perm filename Z[AM,DBL] blob
sn#386227 filedate 1978-10-06 generic text, type T, neo UTF8
.NSECP(Overview)
.SKIP 4
.OVERV: SECNUM ;
.QQ
Indeed, you can build a machine to draw demonstrative conclusions for you,
but I think you can never build a machine that will draw plausible inferences.
-- Polya
.ESS
.SKIP 4
.SSEC(Abstract of this Thesis)
A program, called "AM", is described which models one aspect of
elementary mathematics research: developing new concepts under the
guidance of a large body of heuristic rules. "Mathematics" is
considered as a type of intelligent behavior, not merely
as a finished
product.
The local heuristics communicate via an agenda mechanism, a global
list of tasks for the system to perform and reasons why each task is
plausible. A single task might direct AM to define a new concept, or
to explore some facet of an existing concept, or to examine some
empirical data for regularities, etc. Repeatedly, the program
selects from the agenda the task having the best supporting reasons,
and then executes it.
Each concept is an active, structured knowledge module. A hundred
very incomplete modules are initially provided, each one
corresponding to an elementary set-theoretic concept (e.g., union).
This provides a definite but immense "space" which AM begins to
explore, guided by a corpus of 250 heuristic rules. AM extends its
knowledge base, ultimately rediscovering hundreds of common concepts
(e.g., numbers) and theorems (e.g., unique factorization).
.SSECP(Five-page Summary of the Project)
Scientists often face the difficult task of formulating nontrivial
research problems which are solvable. In any given branch of
science, it is usually easier to tackle a specific given problem than
to propose interesting yet managable new questions to investigate.
For example, contrast ⊗4solving⊗* the Missionaries and Cannibals
problem with the more ill-defined reasoning which led to
⊗4inventing⊗* it.
This thesis is concerned with creative theory formation in
mathematics: how to propose interesting new concepts and plausible
hypotheses connecting them. The experimental vehicle of my research
is a computer program called ⊗2AM⊗*$$ The original meaning of this
mnemonic has been abandoned. As Exodus states: I ↓_AM_↓ that I
↓_AM_↓. $
Initially, AM is
given the definitions of 115 simple set-theoretic concepts (like
"Delete", "Equality"). Each concept is represented internally as a
data structure with a couple dozen slots or facets (like
"Definition", "Examples", "Worth"). Initially, most facets of most
concepts are blank, and AM uses a collection of 250 heuristics --
plausible rules of thumb -- for guidance, as it tries to fill in
those blanks. Some heuristics are used to select which specific facet
of which specific concept to explore next, while others are used to
actually find some appropriate information about the chosen facet.
Other rules prompt AM to notice simple relationships between known
concepts, to define promising new concepts to investigate, and to
estimate how interesting each concept is.
. SSSEC(Detour: Analysis of a discovery)
Before discussing how to ⊗4synthesize⊗* a new theory, consider
briefly how to ⊗4analyze⊗* one, how to construct a plausible chain of
reasoning which terminates in a given discovery. One can do this by
working backwards, by reducing the creative act to simpler and
simpler creative acts. For example, consider the concept of prime
numbers. How might one be led to define such a notion? Notice the
following plausible strategy:
.ONCE INDENT 9,9,9 SELECT 6
"If f is a function which transforms elements of A into elements of
B, and B is ordered, then consider just those members of A which are
transformed into ⊗4extremal⊗* elements of B. This set is an
interesting subset of A."
When f(x) means "divisors of x", and the ordering is "by length",
this heuristic says to consider those numbers which have a minimal$$
The other extreme, numbers with a MAXIMAL number of factors, was also
proposed by AM as worth investigating. This led AM to many
interesting questions. See Appendix {[2]MAXDIV}. $ number of factors
-- that is, the primes. So this rule actually ⊗4reduces⊗* our task
from "proposing the concept of prime numbers" to the more elementary
problems of "discovering ordering-by-length" and "inventing
divisors-of".
But suppose we know this general rule: ⊗6"If f is an interesting
function, consider its inverse."⊗* It reduces the task of discovering
divisors-of to the simpler task of discovering multiplication$$ Plus
noticing that multiplication is associative and commutative. $.
Eventually, this task reduces to the discovery of very basic notions,
like substitution, set-union, and equality. To explain how a given
researcher might have made a given discovery, such an analysis is
continued until that inductive task is reduced to "discovering"
notions which the researcher already knew, which were his conceptual
primitives.
. SSSEC(What AM does: Syntheses of discoveries)
.QQ
This leads to the paradox that the more original a discovery the more obvious
it seems afterwards.
The creative act is not an act of creation in the sense of the Old Testament.
It does not create something out of nothing; it uncovers, selects, re-shuffles,
combines, synthesizes already existing facts, faculties, skills.
The more familiar the parts, the more striking the new whole.
-- Koestler
.ESS
Suppose a large collection of these heuristic strategies has been
assembled (e.g., by analyzing a great many discoveries, and writing
down new heuristic rules whenever necessary). Instead of using them
to ⊗4explain⊗* how a given idea might have evolved, one can imagine
starting from a basic core of knowledge and "running" the heuristics
to ⊗4generate⊗* new concepts. We're talking about reversing the
process described in the last section: not how to ⊗4explain⊗*
discoveries, but how to ⊗4make⊗* them.
Such syntheses are precisely what AM does. The program consists of a
large corpus of primitive mathematical concepts, each with a few
associated heuristics$$ Situation/action rules which function as
local "plausible move generators". Some suggest tasks for the system
to carry out, some suggest ways of satisfying a given task, etc. $.
AM's activities all serve to expand AM itself, to enlarge upon a
given body of mathematical knowledge. To cope with the enormity of
the potential "search space" involved, AM uses its heuristics as
judgmental criteria to guide development in the most promising
direction. It appears that the process of inventing worthwhile new$$
Typically, "new" means new to AM, not to Mankind; and "worthwhile"
can only be judged in hindsight. $ concepts can be guided
successfully using a collection of a few hundred such heuristics.
Each concept is represented as a frame-like data structure with 25
different facets or slots. The types of facets include: ⊗6Examples,
Definitions, Generalizations, Domain/Range, Analogies,
Interestingness,⊗* and many others. Modular representation of
concepts provides a convenient scheme for organizing the heuristics;
for example, the following strategy fits into the ⊗4Examples⊗* facet
of the ⊗4Predicate⊗* concept: ⊗6"If, empirically, 10 times as many
elements ⊗4fail⊗* some predicate P, as ⊗4satisfy⊗* it, then some
⊗4generalization⊗* (weakened version) of P might be more interesting
than P"⊗1. AM considers this suggestion after trying to fill in
examples of each predicate$$ In fact, after AM attempts to find
examples of SET-EQUALITY, so few are found that AM decides to
generalize that predicate. The result is the creation of
a new predicate which means
"Has-the-same-length-as" -- i.e., a rudimentary precursor to natural
numbers. $.
AM is initially given a collection of 115 core concepts, with only a
few facets filled in for each. Its sole activity is to choose some
facet of some concept, and fill in that particular slot. In so
doing, new notions will often emerge. Uninteresting ones are
forgotten, mildly interesting ones are kept as parts of one facet of
one concept, and very interesting ones are granted full
concept-module status. Each of these new modules has dozens of blank
slots, hence the space of possible actions (blank facets to fill in)
grows rapidly. The same heuristics are used both to suggest new
directions for investigation, and to limit attention: both to sprout
and to prune.
. SSSEC(Results)
The particular mathematical domains in which AM operates depend upon
the choice of initial concepts. Currently, AM begins with nothing
but a scanty knowledge of concepts which Piaget might describe as
⊗4prenumerical⊗*: Sets, substitution, operations, equality, and so
on. In particular, AM is not told anything about proof,
single-valued functions, or numbers.
From this primitive basis, AM quickly discovered$$ "Discovering" a
concept means that (1) AM recognized it as a distinguished entity
(e.g., by formulating its definition) and also (2) AM decided it was
worth investigating (either because of the interesting way it was
formed, or because of surprising preliminary empirical results). $
elementary numerical concepts (corresponding to those we refer to as
natural numbers, multiplication, factors, and primes) and wandered
around in the domain of elementary number theory. AM was not designed
to ⊗4prove⊗* anything, but it did ⊗4conjecture⊗* many well-known
relationships (e.g., the unique factorization theorem).
AM was not able to discover any "new-to-Mankind" mathematics purely
on its own, but ⊗4has⊗* discovered several interesting notions
hitherto unknown to the author. A couple bits of new mathematics have
been ⊗4inspired⊗* by AM.⊗A2⊗* A synergetic AM--human combination can
sometimes produce better research than either could alone.$$ This is
supported by Gelernter's experiences with his geometry program: While
lecturing about how it might prove a certain theorem about isosceles
triangles, he came up with a new, cute proof. Similarly, Guard and
Eastman noticed an intermediate result of their SAM resolution
theorem prover, and wisely interpreted it as a nontrivial result in
lattice theory (now known as SAM's lemma). $ Although most of the
concepts AM proposed and developed were already very well known, AM
defined some of them in novel ways (e.g., prime pairs were defined by
restricting addition to primes; that is, for which primes p,q,r is it
possible that p+q=r?$$ The answer is that either p or q must be 2,
and that the other two primes are a prime pair -- i.e., they differ
by two. $).
Everything that AM does can be viewed as testing the underlying body
of heuristic rules. Gradually, this knowledge becomes better
organized, its implications clearer. The resultant body of detailed
heuristics may be the germ of a more efficient programme for
educating math students than the current dogma$$ Currently, an
educator takes the very best work any mathematician has ever done,
polishes it until its brilliance is blinding, then presents it to the
student to induce upon. Many individuals (e.g., Knuth and Polya) have
pointed out this blunder. A few (e.g., Papert at MIT, Adams at
Stanford) are experimenting with more realistic strategies for
"teaching" creativity. See the references by these authors in the bibliography. $.
Another benefit of actually constructing AM is that of
⊗4experimentation⊗*: one can vary the concepts AM starts with, vary
the heuristics available, etc., and study the effects on AM's
behavior. Several such experiments were performed. One involved
adding a couple dozen new concepts from an entirely new domain: plane
geometry. AM busied itself exploring elementary geometric concepts,
and was almost as productive there as in its original domain. New
concepts were defined, and new conjectures formulated. Other
experiments indicated that AM was more robust than anticipated; it
withstood many kinds of "de-tuning". Others demonstrated the
tremendous impact that a few key concepts (e.g., Equality) had on
AM's behavior. Several more experiments and extensions have been
planned for the future.
.if wantmotiv then start;
. SSSEC(Motivation [optional])
.QQ
We need a super-mathematics in which the operations are as unknown as
the quantities they operate on, and a super-mathematician, who does
not know what he is doing when he performs these operations.
-- Eddington
.ESS
Although the motivation for carrying out this research of course
preceded the effort, I have delayed until this section a discussion
of why this is worthwhile, why it was attempted.
First there was the inherent interest of getting a handle on
scientific creativity. AM is partly a demonstration that some
aspects of creative theory formation can be demystified, can be
modelled as simple rule-governed behavior.
Related to this is the potential for learning from AM more about the
processes of concept formation. This was touched on previously, and
several experiments already performed on AM will be detailed later.
Third, AM itself may grow into something of pragmatic value. Perhaps
it will become a useful tool for mathematicians, for educators, or as
a model for similar systems in more "practical" fields. Perhaps in the
future we scientists will be able to rely on automated assistants to
carry out the "hack" phases of research, the tiresome legwork
necessary for "secondary" creativity.
Historically, the domain of AM came from a search for a scientific
field whose activities had no specific goal, and in which natural
language abilities were unnecessary. This was to test out the BEINGs
[Lenat 75b]
ideas for a modular representation of knowledge.
It would be unfair not to mention the usual bad reasons for this
research: the "Look ma, no hands" syndrome, the AI researcher's
classic maternal urges, ego, the usual thesis drives, etc.
.end;
. SSSEC(Conclusions)
AM is forced to judge ⊗4a priori⊗* the value of each new concept, to
lose interest quickly in concepts which aren't going to develop into
anything. Often, such judgments can only be based on hindsight. For
similar reasons, AM has difficulty formulating new heuristics which
are relevant to the new concepts it creates. Heuristics are often
merely compiled hindsight. While AM's "approach" to empirical
research may be used in other scientific domains, the main limitation
(reliance on hindsight) will probably recur. This prevents AM from
progressing indefinitely far on its own.
This ultimate limitation was reached. AM's performance degraded more
and more as it progressed further away from its initial base of
concepts. Nevertheless, AM demonstrated that selected aspects of
creative discovery in elementary mathematics could be adequately
represented as a heuristic search process. Actually constructing a
computer model of this activity has provided an experimental vehicle
for studying the dynamics of plausible empirical inference.
.SSEC(Ways of viewing AM as some common process)
This section will provide a few metaphors: some hints for squeezing
AM into paradigms with which the reader might be familiar. For
example, the existence of heuristics in AM is functionally the same
as the presence of domain-specific information in any knowledge-based
system.
Consider assumptions, axioms, definitions, and theorems to be
syntactic rules for the language that we call Mathematics. Thus
theorem-proving, and the whole of textbook mathematics, is a purely
syntactic process. Then the heuristic rules used by a mathematician
(and by AM) would correspond to the semantic knowledge associated
with these more formal methods.
Just as one can upgrade natural-language-understanding by
incorporating semantic knowledge, so AM is only as successful as the
heuristics it knows.
Four more ways of "viewing" AM as something else will be provided:
(i) AM as a hill-climber, (ii) AM as a heuristic search program,
(iii) AM as a mathematician, and (iv) AM as half a book.
. SSSEC(AM as Hill-climbing)
Let's draw an analogy between
the process of
developing new mathematics and the familiar
process of hill-climbing. We may visualize AM as exploring a space
using a measuring or "evaluation" function which imparts to it a topography.
Consider AM's core of very simple knowledge. By compounding its
known concepts and methods, AM can explore beyond the frontier of
this foundation a little
wherever it wishes. The incredible variety of alternatives to
investigate includes all known mathematics, much trivia, countless
deadends, and so on. The only "successful" paths near the core are
the narrow ridges of known mathematics (plus perhaps a few
as-yet-undiscovered isolated peaks).
How can AM walk through this immense space, with any hope of
following the few, slender trails of already-established
mathematics (or some equally successful new fields)? AM must do
hill-climbing: As new concepts are formed, decide how promising they
are, and always explore the currently most-promising new concept. The
evaluation function is quite nontrivial, and this thesis may be
viewed as an attempt to study and explain and duplicate the
judgmental criteria people employ. Preliminary attempts$$
These took the form of informal simulations. Although far from controlled
experiments, they indicated the feasability of attempting to create AM,
by yielding an approximate figure for the amount of informal knowledge
such a system would need.
$ at codifying such
"mysterious" emotive forces as intuition, aesthetics, utility,
richness, interestingness, relevance... indicated that a large but
not unmanageable collection of heuristic rules should suffice.
The important visualization to make is that with proper evaluation
criteria, AM's planar mass of interrelated concepts is transformed
into a three-dimensional relief map: the known lines of development
become mountain ranges, soaring above the vast flat plains of trivia
and inconsistency below.
Occasionally an isolated hill is discovered near the core;$$ E.g.,
Conway's numbers, as described in [Knuth 74]. $
certainly whole ranges lie undiscovered for long periods of time$$
E.g., non-Euclidean geometries weren't thought of until 1848. $, and
the terrrain far from the initial core is not yet explored at all.
. SSSEC(AM as Heuristic Search)
We earlier referred to AM as a
kind of "heuristic search" program. That must mean that AM is
exploring a particular "space," using some informal evaluation
criteria to guide it.
The flavor of search which is used here is that of progressively
enlarging a tree. Certain "evaluation-function" heuristics are used
to decide which node of the tree to expand next, and other guiding
rules are then used to produce from that node a few interesting
successor nodes. To do mathematical research well, I claim that it is
necessary and sufficent to have good methods for proposing new
concepts from existing ones, and for deciding how interesting each
"node" (partially-studied concept) is.
AM is initially supplied with a few facts about some simple math
concepts. AM then explores mathematics by selectively enlarging that
basis. One could say that AM consists of an active body of
mathematical concepts, plus enough "wisdom" to use and develop them
effectively. For "wisdom", read "heuristics". Loosely speaking, then,
AM is a heuristic search program. To see this more clearly, we must
explain what the nodes of AM's search space are, what the successor
operators or links are, and what the evaluation function is.
AM's space can be considered to consist of all nodes which are
consistent, partially-filled-in concepts. Then a primitive "legal
move" for AM would be to (i) enlarge some facet of some concept, or
(ii) create a new, partially-complete concept. Consider momentarily
the size of this space. If there were no constraint on what the new
concepts can be, and no informal knowledge for quickly finding
entries for a desired facet, a blind "legal-move" program would go
nowhere -- slowly! One shouldn't even call the activity such a
program would be doing "math research."
The heuristic rules are used as little "plausible move generators".
They suggest which facet of which concept to enlarge next, and they
suggest specific new concepts to create. The only activities which AM
will consider doing are those which have been motivated for some
specific good$$ Of course, AM thinks a reason is "good" if -- and
only if -- it was told that by a heuristic rule; so those rules had
better be plausible, preferably the ones actually used by the
experts. $ reason. A global ⊗4agenda of tasks⊗* is maintained,
listing all the activities suggested but not yet worked on.
AM has a definite algorithm for rating the nodes of its space. Many
heuristics exist merely to estimate the worth of any given concept.
Other heuristics use these worth ratings to order the tasks on the
global agenda list. Yet AM has no specific goal criteria: it can
never "halt", never succeed or fail in any absolute sense. AM goes on
forever$$ Technically, forever is about 100,000 list cells and a
couple cpu hours. $.
Consider Nilsson's descriptions of depth-first searching and
breadth-first searching
([Nilsson 71]).
He has us maintain a list of "open" nodes.
Repeatedly, he plucks the top one and expands it. In the process,
some new nodes may be added to the Open list. In the case of
depth-first searching, they are added at the top; the next node to
expand is the one most recently created; the Open-list is being used
as a push-down stack. For breadth-first search, new nodes are added
at the bottom; they aren't expanded until all the older nodes have
been; the Open-list is used as a queue. For heuristic search, or
"best-first" search, new nodes are evaluated in some numeric way, and
then "merged" into the already-sorted list of Open nodes.
.ONCE TURN ON "{}"
This process is very similar to the agenda mechanism AM uses to
manage its search. This will be discussed in detail in Chapter
{[2]AGENDA}. Each entry on the agenda consists of three parts:
(i) a plausible task for AM
to do, (ii) a list of reasons supporting that task, and (iii) a
numeric estimate of the overall priority this task should have.
When a task is suggested for some reason, it is added to the agenda.
A task may be suggested several times, for different reasons. The
global priority value assigned to each task is based on the combined
value of its reasons. The control structure of AM is simply to
select the task with the highest priority, execute it, and select a
new one. The agenda mechanism appears to be a very well-suited data
structure for managing a "best-first" search process.
Similar control structures were used in LT
[Newell, Shaw, & Simon 57], the predictor part of
Dendral
[Buchanan et al 69], SIMULA-67 [Dahl 68],
and KRL [Bobrow & Winograd
77].
The main difference is that in AM, symbolic reasons are
used (albeit in trivial token-like ways) to decide whether -- and how
much -- to boost the priority of a task when it is suggested again.
There are several difficulties and anomalies in forcing AM into the
heuristic search paradigm.
In a typical heuristic search
(e.g., Dendral [Feigenbaum et al 71], Meta-Dendral [Buchanan et al 72],
most game-playing programs [Samuel 67]),
a "search space" is defined implicitly by a
"legal move generator". Heuristics are present to constrain that
generator so that only plausible nodes are produced.
The second kind of heuristic
search, of which AM is an example, contains no "legal move generator".
Instead,
AM's heuristics are used as plausible
move generators.
Those heuristics themselves implicitly define the possible tasks AM might
consider, and ⊗4all⊗* such tasks should be plausible one. In the first kind of
search, removing a heuristic widens the search space; in AM's kind of
search, removing a heuristic ⊗4reduces⊗* it.
.HSEARCH: PAGE;
Another anomaly is that the operators which AM uses to enlarge and
explore the space of concepts are themselves mathematical concepts
(e.g., some heuristic rules result in the creation of new heuristic
rules; "Compose" is both a concept and an operation which results in
new concepts). Thus AM should be viewed as a mass of knowledge which
enlarges ⊗4itself⊗* repeatedly. Typically,
computer programs keep the information they "discover" quite
separate from the knowledge they use to make discoveries$$ Of course
this is often because the two kinds of knowledge are very
different: For a chess-player, the first kind is "good board
positions," and the second is "strategies for making a good move."
Theorem-provers are an exception. They produce
a new theorem, and then use it (almost like a new operator) in future proofs.
A program to learn
to play checkers [Samuel 67] has this same flavor, thereby indicating that
this `self-help' property is not a function of the task
domain, not simply a characteristic of mathematics. $
Perhaps the greatest difference between AM and typical heuristic
search procedures is that AM has no well-defined target concepts or
target relationships. Rather, its "goal criterion" -- its sole aim
-- is to maximize the interestingness level of the activities it
performs, the priority ratings of the top tasks on the agenda. It
doesn't matter precisely which definitions or conjectures AM
discovers -- or misses -- so long as it spends its time on plausible
tasks. There is no fixed set of theorems that AM should discover, so
AM is not a typical ⊗4problem-solver⊗*. There is no fixed set of
traps AM should avoid,
no small set of legal moves,
and no winning/losing behavior,
so AM is not a
typical ⊗4game-player⊗*.
For example, no stigma is attached to the fact that AM never
discovered real numbers$$ There are many "nice" things which AM
didn't -- and can't -- do: e.g., devising ↓_geometric_↓ concepts from
its initial simple set-theoretic knowledge. See the discussion of
the limitations of AM, Section {[2]DIFSECNUM}.{[2]DIFSSECNUM}. $; it
was rather surprising that AM managed to discover ⊗4natural⊗*
numbers! Even if it hadn't done that, it would have been
acceptable$$ Acceptable to whom? Is there really a domain-invariant
criterion for judging the quality of AM's actions? See the
discussions in Section {[2]EVALU}.1. $ if AM had simply gone off and
developed ideas in set theory.
. SSSEC(AM as a Mathematician)
.AMAM: PAGE;
.AMAMSSEC: SSECNUM;
Before diving into the innards of AM, let's take a moment to discuss
the totality of the mathematics which AM carried out. Like a
contemporary historian summarizing the work of the Babylonian
mathematicians, we shan't hesitate to use current terms and criticize
by current standards.
AM began its investigations with scanty knowledge of a few
set-theoretic concepts (sets, equality of sets, set operations).
Most of the obvious set-theory relations (e.g., de Morgan's laws)
were eventually uncovered; since AM never fully understood abstract
algebra, the statement and verification of each of these was quite
obscure. AM never derived a formal notion of infinity, but it
naively established conjectures like "a set can never be a member of
itself", and procedures for making chains of new sets ("insert a set
into itself"). No sophisticated set theory (e.g., diagonalization)
was ever done.
After this initial period of exploration, AM decided that "equality"
was worth generalizing, and thereby discovered the relation
"same-size-as". "Natural numbers" were based on this, and soon most
simple arithmetic operations were defined.
Since addition arose as an analog to union, and multiplication as a
repeated substitution followed by a generalized kind of unioning$$
Take two bags A and B. Replace each element of A by the bag B. Remove
one level of parentheses by taking the union of all elements of the
transfigured bag A. Then that new bag will have as many elements as
the product of the lengths of the two original bags. $ it came as
quite a surprise when AM noticed that they were related (namely,
N+N=2⊗7x⊗*N). AM later re-discovered multiplication in three other ways:
as repeated addition, as the numeric analog of the Cartesian product
of sets, and by studying the cardinality of power sets$$ The size of
the set of all subsets of S is 2↑|↑S↑|. Thus the power set of A∪B has
length equal to the ↓_product_↓ of the lengths of the power sets of A
and B individually (assuming A and B are disjoint). $. These
operations were defined in different ways, so it was an unexpected
(to AM) discovery when they all turned out to be equivalent. These
surprises caused AM to give the concept `Times' quite a high Worth
rating.
Exponentiation was defined as repeated multiplication. Unfortunately,
AM never found any obvious properties of exponentiation, hence lost
all interest in it.
Soon after defining multiplication, AM investigated the process of
multiplying a number by itself: squaring. The inverse of this turned
out to be interesting, and led to the definition of square-root. AM
remained content to play around with the concept of
⊗4integer⊗*-square-root. Although it isolated the set of numbers
which had no square root, AM was never close to discovering
rationals, let alone irrationals.
Raising to fourth-powers, and fourth-rooting, were discovered at this
time. Perfect squares and perfect fourth-powers were isolated. Many
other numeric operations and kinds of numbers were isolated: Odds,
Evens, Doubling, Halving, etc. Primitive notions of numeric
inequality were defined but AM never even discovered Trichotomy.
.ONCE TURN ON "{}"
The associativity and commutativity of multiplication indicated that
it could accept a BAG of numbers as its argument. When AM defined
the inverse operation corresponding to Times, this property allowed
the definition to be: "any ⊗4bag⊗* of numbers (>1) whose product is
x". This was just the notion of factoring a number x.
Minimally-factorable numbers turned out to be what we call primes.
Maximally-factorable numbers were also thought to be interesting.
Prime pairs were discovered in a bizarre way: by restricting addition
(its arguments and its values) to Primes.$$ That is, consider the set
of triples p,q,r, all primes, for which p+q=r. Then one of them must
be "2", and the other two must therefore form a prime pair. $ AM
conjectured the fundamental theorem of arithmetic (unique
factorization into primes) and Goldbach's conjecture (every even
number >2 is the sum of two primes) in a surprisingly symmetric way.
The unary representation of numbers gave way to a representation as a
bag of primes (based on unique factorization), but AM never thought
of exponential notation.
$$ A tangential note:
All of the discoveries mentioned above were made by AM working
by itself, with a human being observing its behavior. If the
level of sophistication of AM's concepts were higher (or the level
of sophistication of its users were lower), then it might be worthwhile
to develop a nice user--system interface. The user in that case
could -- and ought to -- work right along with AM as a co-researcher. $
Since the key concepts of remainder,
greater-than, gcd, and exponentiation were never mastered, progress
in number theory was arrested.
When a new base of ⊗4geometric⊗* concepts was added, AM began finding
some more general associations. In place of the strict definitions
for the equality of lines, angles, and triangles, came new
definitions of concepts we refer to as Parallel, Equal-measure,
Similar, Congruent, Translation, Rotation, plus many which have no
common name (e.g. the relationship of two triangles sharing a common
angle). A cute geometric interpretation of Goldbach's conjecture was
found$$ Given all angles of a prime number of degrees,
(0,1,2,3,5,7,11,...,179 degrees), then any angle between 0 and 180
degrees can be approximated (to within 1 degree) as the sum of two of
those angles. $. Lacking a geometry "model" (an analogic
representation like the one Gelernter employed), AM was doomed to
failure with respect to proposing only plausible geometric
conjectures.
Similar restrictions due to poor "visualization" abilities would crop
up in topology. The concepts of continuity, infinity, and measure
would have to be fed to AM before it could enter the domains of
analysis. More and more drastic changes in its initial base would be
required, as the desired domain gets further and further from simple
finite set theory and elementary number theory.
. SKIP TO COLUMN 1; SSSEC(AM as a Thesis [optional])
.QQ
Walking home along a deserted street late at night, the reader may
imagine himself to feel in the small of his back a cold, hard object;
and to hear the words spoken behind him, `Easy now. This is a
stick-up. Hand over your money.' What does the reader do? He
attempts to generate the utterance. He says to himself, now if I were
standing behind someone holding a cold, hard object against his
back, what would make me say that? What would I mean by it? The
reader is advised that he can only arrive at the deep structure of
this book, and through the deep structure the semantics, if he
attempts to generate the book for himself. The author wishes him
luck.
-- Linderholm
.ESS
. TURN ON "{}";
Don't be scared by the weight of the document you're now holding.
If you flip to page {[3]ENDTEXT}, you'll see that the last two-thirds
are just appendices.
Each chapter is of roughly equal importance, which explains the huge variation
in length.
Start looking over Chapter {[2]EXAM1} right away: it contains
a detailed example of what AM does.
Since you're reading this sentence now, we'll assume that
you want a preview of
what's to come in the rest of this document.
Chapter 3 covers the top-level control structure of the system, which is
based around the notion of an `agenda' of tasks to perform.
In Chapter 4 the low-level control structure is revealed: AM is really
guided by a mass of heuristic rules of varying generality.
Chapter 5 contains more than you want to know about the representation
of knowledge in AM.
The diagram showing some of AM's starting concepts
(page {[3]TREECON}) is worth a look, even out of context.
Most of the results of the project are presented in Chapter 6. In addition to
simply `running' AM, several experiments have been conducted with it.
It's awkward to evaluate AM, and therefore Chapter 7 is quite long and detailed.
The appendices provide material which supplements the text.
Appendix {[2]ALLCON} contains a description of all the initial concepts,
some examples of how they were coded into Lisp, and a partial list of the
concepts AM defined and investigated along the way.
Appendix {[2]ALLHEU} exhibits all {[3]TRULES} heuristics that AM is
explicitly provided with.
Appendix {[2]MAXDIV} is essentially a math article, about the major discovery
that AM motivated: maximally-divisible numbers. Finally,
Appendix {[2]TRACES} contains traces of AM in action: a long prose
description, a long task-by-task description, and a long undoctored transcript
excerpt. Appendix {[2]GLOS} hasn't been mentioned yet, and forms the
subject of the remainder of this section.
This thesis -- and its readers -- must come to grips with a very
interdisciplinary problem. For the reader whose background is in
Artificial Intelligence, most of the system's actions -- the
"mathematics" it does -- may seem inherently uninteresting. For the
mathematician, the word "LISP" signifies nothing beyond a speech
impediment (to Artificial Intelligence types it also connotes a
programming impediment). If I don't describe "LISP" the first time I
mention it, a large fraction of potential readers will never realize
that potential. If I ⊗4do⊗* stop to describe LISP, the other readers
will be bored.
In an attempt not to lose readers due to jargon, two glossaries of
terms have been compiled. Appendix {[2]GLOS}.1 (p. {[3]GLOS1P})
contains capsule descriptions of the mathematical terms, ideas, and
notations used in this thesis. Appendix {[2]GLOS}.2 renders the
analogous service for Artificial Intelligence jargon and computer
science concepts.